// LongestIncreasingSubsequence.cpp : Defines the entry point for the console application.
//
/****************************************************************************************************
/* Author: Shujun Liu
/* Date: 2/12/2012
/* Question:
/* The longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence 
/* of a given sequence such that all elements of the subsequence are sorted in increasing order. For 
/* example, length of LIS for { 10, 22, 9, 33, 21, 50, 41, 60, 80 } is 6 and 
/* LIS is {10, 22, 33, 50, 60, 80}.
/***************************************************************************************************/

#include "stdafx.h"
#include <vector>
using namespace std;

//Version 1.Complexity is O(n2)
int LIS(int arr[], int n)
{
	int * pRet = NULL;
	pRet = new int[n];
	
	 /* Initialize LIS values for all indexes */
	for (int i = 0; i < n; i++ )
    {
		pRet[i] = 1;
	}

	int nMax = 1;
	if(1 == n)
	{
		delete [] pRet;
		pRet = NULL;
		return nMax; 
	}

	for(int i = 1; i< n; i++)
	{
		for(int j = 0; j < i; j++)
		{
			if(arr[j] < arr[i] && pRet[i] < pRet[j] + 1/*This restriction make sure just the longest one was calculated */)
			{
				pRet[i] = pRet[j] + 1;
				
			}
		}
	}

	/* Pick maximum of all LIS values */
	for (int i = 0; i < n; i++ )
	{ 
		if ( nMax < pRet[i] )
		{
			nMax = pRet[i];
		}
	}
	//Free the memory.
	delete [] pRet;
	pRet = NULL;

	return nMax;
}

/*
* Algorithm2 for LIS with time complexity O(nlogn)
* In the solution, the increasing menas strict increase (not include equal)
*/

/*
this routine is to find the lower bound index in range (start, end) which satisfy:
str[t-1]<value<str[t], t is the reutrn value.
*/
int FindLowerBound( int *str, int start, int end, int value )
{
	while( start <= end )
	{
		int mid = (start+end)/2;
		if( str[mid] > value )
			end = mid-1;
		else //( str[mid] <= value )
		{
			start = mid+1;
		}
	}

	//assert( value < str[start] && value > str[start-1] );
	return start;
}

/*
*
* str[] keeps the orignal string
* indexArray[i] is defined as the minimum ended value in LIS with length i, which is strictly increase array
* For example, if str[] is 2 5 3 4, the initia value indexArray[1]=2, then scan from str[1],
* 5>2, get indexArray[2]=5, move to str[2],
* 3<5, then search indexArray[1] to indexArray[2] through binary search, find position t which
* satisfies indexArray[t-1]<str[2]<indexArray[t], search indexArray[2],
* 4>3, get indexArray[3]=4, then the last index of indexArray is the minLis we need to return.
* each iteration need binary search, the time complexity is lgn, then the total should be O(nlgn)
*/
int LIS2( int *str, int size )
{
	if( size < 1 )
		return 0;
	int *indexArray = new int[size];

	int maxLis = 1;
	indexArray[maxLis] = str[0];

	for( int i = 1; i<size; i++ )
	{
		if(str[i] > indexArray[maxLis] )
		{
			maxLis++;
			indexArray[maxLis] = str[i];
		}
		else
		{
			int t = FindLowerBound(indexArray, 1, maxLis, str[i]);
			indexArray[t] = str[i];
		}
	}

	delete [] indexArray;
	return maxLis;
}

int _tmain(int argc, _TCHAR* argv[])
{
	int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
	int n = sizeof(arr)/sizeof(arr[0]);

	for( int i =0; i<n; i++ )
		printf("%d ",arr[i]);

	printf("\nAlgorithm1: LIS is %d", LIS( arr, n));	
	printf("\nAlgorithm2: LIS is %d\n\n", LIS2( arr, n));	

 	int arr2[] = { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 2, 7 };
	n = sizeof(arr2)/sizeof(arr2[0]);
    
	for( int i =0; i<n; i++ )
		printf("%d ",arr2[i]);

	printf("\nAlgorithm1: LIS is %d", LIS( arr, n));	
	printf("\nAlgorithm2: LIS is %d\n", LIS2( arr, n));	

	printf("Press any key to terminate...\n");
	return getchar();
}

